/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //这个函数用于返回链表长度
    int return_len(ListNode* l1)
    {
        if(l1->val==0&&l1->next==nullptr)
        {
            return 0;
        }
        else
        {
            ListNode* p=l1;

            int len=0;
            while(p!=nullptr)
            {
                len++;
                p=p->next;
            }
           
            return len;
        }
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* l=new ListNode;
        ListNode* p=new ListNode;
        //保证l1是长的，l2是短的
        int lon=return_len(l1);
        int min=return_len(l2);
        if(lon<min)
        {
            p=l1;
            lon=min;
            l1=l2;
            l2=p;
        }
        //为短的补0
        p=l2;
        int lon1=lon;
        //为短的链表按长的补齐0
        while(lon1>1)
        {
            
            if(p->next==nullptr)
            {
                p->next=new ListNode;
            }
            p=p->next;
            lon1--;
        }
        //进位数组，表示的是第i位相加时有无发生进位，即相加时要看i-1是否进位
        bool*jinwei=new bool[lon];
        p=l1;
        ListNode* p2=l2;
        int i,c;
        //两个链表共同前进，循环以长度为终止条件
        for(i=0;i<lon;i++)
        {
            c=p->val+p2->val;
            //这个不用看进位所以特殊处理
            if(i==0)
            {
                if(c>9)
                {
                    jinwei[0]=true;
                    p->val=c-10;
                }
                else
                {
                    jinwei[0]=false;
                    p->val=c;
                }
            }
            else
            {
                //先看上一个进位对这个数值的影响
                if(jinwei[i-1]==true)
                {
                    p->val=c+1;
                    
                }
                else
                {
                    p->val=c;
                }
                //再看本次最终数值是否产生进位，如果产生就-10即可
                if(p->val>9)
                {
                    p->val=p->val-10;
                    jinwei[i]=true;
                }
                else
                {
                    jinwei[i]=false;
                }
            }
            //同样的最后一位发生了进位要特殊处理，新增一个数值为1的节点。
            if(i==lon-1&&jinwei[i]==1)
            {
                p->next=new ListNode(1);
            }
            p=p->next;
            p2=p2->next;
        }
        return l1;
    }
};